package day13;

import java.util.HashMap;
import java.util.Scanner;
import java.util.TreeMap;

public class demo3 {
    public static void main(String[] args) {
      String str="abcdd";
        System.out.println(rearrangestring(str));
    }

    public static String rearrangestring (String str) {
        char[]chars = str.toCharArray();
        int[]arr = new int[26];
        int n = chars.length;
        int Maxcount = 0;
        int Max = 0;
        for (int i = 0; i < n ; i++) {
            arr[chars[i] - 'a']++;
            if (arr[chars[i] - 'a'] > Maxcount) {
                Maxcount = arr[chars[i] - 'a'];
                Max = chars[i] - 'a';
            }
        }
        if (((n + 1) / 2) <Maxcount) {
            return "";
        }
        char[]ret = new char[n];
        int i = 0;
        while (Maxcount-- > 0) {
            ret[i] = (char)(Max + 'a');
            i+=2;
        }

        for (int j = 0; j < 26 ; j++) {
            if (j != Max && arr[j] > 0) {
                while (arr[j]-- > 0) {
                    if (i > n)i = 1;
                    ret[i] = (char)(j + 'a');
                    i += 2;
                }
            }
        }
        return String.valueOf(ret);
    }


}
